package its.opt.graphs;

import its.opt.structures.IntStack;

/**
 * the definition of class OrientedGraph for manipulation with oriented graphs
 * 
 * @author Rafal Hladyszowski
 * 
 */
public class OrientedGraph {

	private int N; // the number of vertices
	private int N2; // N square
	private byte[][] coincidence; // the coincidence matrix
	private byte[][] path; // the matrix for maintanance of paths
	private int[] numIn; // the number of incoming vertices
	private int[] numOut; // the number of outcoming vertices
	private int[] mark; // the array for vertex-marks
	private int[][] parentList; // the list of parents for each node

	public OrientedGraph(int n) {

		// set the number of vertices

		N = n;
		N2 = N * N;

		// allocate memory for coincidence, path, and parentList matrices

		coincidence = new byte[N][N];
		path = new byte[N][N];
		parentList = new int[N][N];

		// allocate memory for the number of incoming and outcoming edges

		numIn = new int[N];
		numOut = new int[N];

		// allocate memory for vertex-marks

		mark = new int[n];

		// set this graph to an empy graph

		removeAllEdges();

		// unmark all vertices

		removeAllMarks();
	}

	public int size() {
		return N;
	}

	public int addEdge(int i, int j) {
		int k, l;

		// is the edge already present?

		if (coincidence[i][j] != 0)
			return 1;

		// connect the vertices and update the list of parents

		coincidence[i][j] = 1;
		parentList[j][numIn[j]] = i;
		numOut[i]++;
		numIn[j]++;
		path[i][j] = 1;

		// update the path matrix

		for (k = 0; k < N; k++)
			if (path[k][i] != 0)
				for (l = 0; l < N; l++)
					if ((l != k) && (path[j][l] != 0))
						path[k][l] = 1;

		return 1;
	}

	public int removeEdge(int i, int j) {
		int k;
		int l, m;
		char added;
		IntStack from, to, from2, to2;

		// is the edge present?

		if (coincidence[i][j] == 0)
			return 1;

		// initialize stacks (needed later)

		from = new IntStack(N2);
		to = new IntStack(N2);
		from2 = new IntStack(N2);
		to2 = new IntStack(N2);

		// remove the edge

		coincidence[i][j] = 0;
		numOut[i]--;
		numIn[j]--;

		// update the list of parents

		for (k = 0; k <= numIn[j]; k++)
			if (parentList[j][k] == i)
				if (k < numIn[j])
					parentList[j][k] = parentList[j][numIn[j]];

		// update the path matrix

		// a) remove all paths that could possibly be wrong

		for (k = 0; k < N; k++)
			if (path[k][i] != 0)
				for (l = 0; l < N; l++)
					if ((l != k) && (coincidence[k][l] == 0) && (path[j][l] != 0)) {
						path[k][l] = 0;
						from.push(k);
						to.push(l);
					}

		// b) add all paths that were potentially removed incorrectly

		do {
			added = 0;

			while (from.notEmpty()) {
				k = from.pop();
				l = to.pop();

				for (m = 0; m < N; m++)
					if ((path[k][m] != 0) && (path[m][l] != 0)) {
						path[k][l] = 1;
						added = 1;
					}

				if (path[k][l] == 0) {
					from2.push(k);
					to2.push(l);
				}
			}

			// swap stacks

			// swapPointers((void**) &from, (void**) &from2);
			IntStack temp = from;
			from = from2;
			from2 = temp;

			// swapPointers((void**) &to, (void**) &to2);
			temp = to;
			to = to2;
			to2 = temp;

		} while (added != 0);

		// get back

		return 1;
	}

	public int reverseEdge(int i, int j) {
		if (canReverseEdge(i, j)) {
			removeEdge(i, j);
			return addEdge(j, i);
		} else
			return 0;
	}

	public boolean canReverseEdge(int i, int j) {
		return connected(i, j);
	}

	public int removeAllEdges() {
		for (int i = 0; i < N; i++) {
			path[i][i] = 1;
			numIn[i] = 0;
			numOut[i] = 0;
			for (int j = 0; j < i; j++)
				coincidence[i][j] = coincidence[j][i] = path[i][j] = path[j][i] = 0;
		}

		return 1;
	}

	public int setMark(int i, int val) {
		mark[i] = val;
		return 1;
	}

	public int setAllMarks(int val) {
		int i;

		for (i = 0; i < N; i++)
			mark[i] = val;

		return 1;
	}

	public int removeMark(int i) {
		mark[i] = 0;
		return 1;
	}

	public int removeAllMarks() {
		int i;

		for (i = 0; i < N; i++)
			mark[i] = 0;

		return 1;
	}

	public int getNumberOfVertices() {
		return N;
	}

	public boolean connected(int i, int j) {
		return (coincidence[i][j] != 0);
	}

	public boolean existsPath(int i, int j) {
		return (path[i][j] != 0);
	}

	public int getNumIn(int i) {
		return numIn[i];
	}

	public int getNumOut(int i) {
		return numOut[i];
	}

	public int getMark(int i) {
		return mark[i];
	}

	public int[] getParentList(int i) {
		return parentList[i];
	}

	public boolean notConnected(int i, int j) {
		return (coincidence[i][j] == 0);
	}
}
